import copy


class Solution(object):
    def maxSideLength(self, mat, threshold):
        m = len(mat)
        n = len(mat[0])
        pre_h = copy.deepcopy(mat)
        pre_v = copy.deepcopy(mat)
        for i in range(m):
            for j in range(1, n):
                pre_h[i][j] += pre_h[i][j - 1]
        for j in range(n):
            for i in range(1, m):
                pre_v[i][j] += pre_v[i - 1][j]

        def cal(k):
            if k == 0:
                return 0
            min_s = float('inf')
            for i in range(m - k + 1):
                if i == 0:
                    s = 0
                    for t in range(k):
                        s += pre_h[i + t][k - 1]
                    base_s = s
                else:
                    base_s -= pre_h[i - 1][k - 1]
                    base_s += pre_h[i + k - 1][k - 1]
                    s = base_s
                min_s = min(min_s, s)
                for j in range(n - k):
                    if i == 0:
                        s -= pre_v[i + k - 1][j]
                        s += pre_v[i + k - 1][j + k]
                    else:
                        s -= (pre_v[i + k - 1][j] - pre_v[i - 1][j])
                        s += (pre_v[i + k - 1][j + k] - pre_v[i - 1][j + k])
                    min_s = min(min_s, s)
            return min_s

        left = 0
        right = min(m, n)
        while left < right:
            mid = (left + right + 1) // 2
            if cal(mid) <= threshold:
                left = mid
            else:
                right = mid - 1
        return left


data = Solution()
mat = [[18, 70], [61, 1], [25, 85], [14, 40], [11, 96], [97, 96], [63, 45]]
threshold = 40184
print(data.maxSideLength(mat, threshold))
